
#include <stdio.h>
#include <stdbool.h>
#include <string.h>

//  (m*11 + a0) + b0
//  (n*11 + a1) + b1




typedef struct
{
	int b0;
	int b1;
	bool isChanged;
	int a0;
	int a1;
}solution_policy;

int count_steps(solution_policy* p_policy)
{
	if (p_policy->isChanged)
	{
		return 100 + p_policy->b1 - p_policy->b0;
	}
	else
	{
		return p_policy->b1 - p_policy->b0;
	}
}

void print_policy(solution_policy* p_policy)
{
	if (p_policy->isChanged)
	{
		int range = 100 + p_policy->b1 - p_policy->b0;
		printf("Changed:\t%02d+%02d -> %02d+%02d\t%02d\r\n",
			p_policy->a0,
			p_policy->b0,
			p_policy->a1,
			p_policy->b1,
			range);
	}
	else
	{
		int range = p_policy->b1 - p_policy->b0;
		printf("NotChanged:\t%02d+%02d -> %02d+%02d\t%02d\r\n",
			p_policy->a0,
			p_policy->b0,
			p_policy->a1,
			p_policy->b1,
			range);
	}
}

bool isCheckPassed(solution_policy* p_policy)
{
	int sum_target;
	int sum_base;
	int range;
	if (p_policy->isChanged)
	{
		sum_target = p_policy->a1 + (p_policy->b1 / 10) + (p_policy->b1 % 10);
		sum_base = p_policy->a0 + (p_policy->b0 / 10) + (p_policy->b0 % 10);
	}
	else
	{
		sum_target = (p_policy->b1 / 10) + (p_policy->b1 % 10);
		sum_base = (p_policy->b0 / 10) + (p_policy->b0 % 10);
	}
#if 0
	if (((sum_base % 11) == 0)&&((sum_target%11) == 0))
	{
		return true;
	}
	else
	{
		return false;
	}
#else
	range = sum_target + 110 - sum_base;
	if ((range % 11) == 0)
	{
		//print_policy(p_policy);
		return true;
	}
	else
	{
		return false;
	}
#endif
}

static solution_policy policy_targets[10000];
static int policy_counter = 0;

void next_check_point_when_fail(solution_policy * p_current, bool* isFailed)
{
	*isFailed = false;
	int base = p_current->isChanged ? 100:0;
	base = base + p_current->b1;

	if (base - p_current->b0 >= 99)
	{
		*isFailed = true;
		return;
	}

	if (base == 99)
	{
		p_current->a0 = 0;
		p_current->a1 = 0;
		p_current->isChanged = true;
		p_current->b1 = 0;
	}
	else if (base < 99)
	{
		p_current->b1++;
	}
	else
	{
		p_current->b1++;
		//if (p_current->a1 == 10)
		//{
		//	if (p_current->a0 >= 10)
		//	{
		//		*isFailed = true;
		//		return;
		//	}
		//	else
		//	{
		//		p_current->a0++;
		//		p_current->a1 = 0;
		//	}
		//}
	}
}

void next_check_point_when_passed(solution_policy * p_current, bool* isEnded)
{
	*isEnded = false;
	int base = p_current->isChanged ? 100 : 0;
	base += p_current->b1;
	if (base >= 100)
	{
		if (p_current->a1 >= 10)
		{
			if (p_current->a0 >= 10)
			{
				if (p_current->b0 >= 99)
				{
					*isEnded = true;
					return;
				}
				else 
				{
					p_current->b0++;
					base = p_current->b0 + 1;
					p_current->a0 = 0;
					p_current->a1 = 0;
				}
			}
			else
			{
				p_current->a0++;
				p_current->a1 = 0;
				p_current->b1 = 0;
			}
		}
		else
		{
			p_current->a1++;
			p_current->b1 = 0;
		}
	}
	else
	{
		if (p_current->b0 >= 99)
		{
			*isEnded = true;
			return;
		}
		
		p_current->b0++;
		p_current->b1 = p_current->b0 + 1;
	}
}

void solution(void)
{
	solution_policy current = 
	{
		.b0 = 0,
		.b1 = 0,
		.isChanged = false,
		.a0 = 0,
		.a1 = 0,
	};
	bool isChecked;
	bool isFailed;
	bool isEnded;

	do
	{
		isChecked = isCheckPassed(&current);
		if (isChecked)
		{
			policy_targets[policy_counter++] = current;
			next_check_point_when_passed(&current, &isEnded);
			if (isEnded)
			{
				break;
			}
		}
		else
		{
			next_check_point_when_fail(&current, &isFailed);
			if (isFailed)
			{
				//printf("should not be here\r\n");
				//getchar();
				continue;
			}
		}
	} while (true);

	printf("solution counts:%d\r\n", policy_counter);
}

void check_test_policy(void)
{

	solution_policy p_test_cases[] =
	{
		[0] = {
			.b0 = 0,
			.b1 = 29,
			.isChanged = false,
			.a0 = 0,
			.a1 = 0,
		},
		[1] = {
			.b0 = 0,
			.b1 = 28,
			.isChanged = false,
			.a0 = 0,
			.a1 = 0,
		},
		[2] = {
			.b0 = 0,
			.b1 = 1,
			.isChanged = true,
			.a0 = 10,
			.a1 = 9,
		},
		[3] = {
			.b0 = 90,
			.b1 = 3,
			.isChanged = true,
			.a0 = 2,
			.a1 = 8,
		},
	};

	for (int i = 0; i < sizeof(p_test_cases) / sizeof(solution_policy); i++)
	{
		bool passed = isCheckPassed(&p_test_cases[i]);
		if (!passed)
		{
			printf("Failed at %d\r\n", i);
		}
	}

	printf("policy_check_verified\r\n");

}

void verify_again(void)
{
	int faild_counter = 0;
	for (int i = 0; i < policy_counter; i++)
	{
		if (!isCheckPassed(&policy_targets[i]))
		{
			printf("failed with:%d\r\n", i);
			faild_counter++;
		}
	}
	if (faild_counter == 0)
	{
		printf("all passed\r\n");
	}
}

void policy_selection(void)
{
	int step_39_counter = 0;
	for (int i = 0; i < policy_counter; i++)
	{
		if (count_steps(&policy_targets[i]) >= 39)
		{
			print_policy(&policy_targets[i]);
		}
	}
}

void print_all_policy(void)
{
	int counters = 0;
	for (int i = 0; i < policy_counter; i++)
	{
		if( (((policy_targets[i].a0 + (policy_targets[i].b0 / 10) + (policy_targets[i].b0 % 10)) % 11) == 0)
			||(!policy_targets[i].isChanged))
		{
			counters++;
			print_policy(&policy_targets[i]);
		}
	}
	printf("Counts:%d, all passed:%d\r\n", policy_counter, counters);
}

int main()
{
	//check_test_policy();
	solution();
	verify_again();
	//policy_selection();
	print_all_policy();
	getchar();

	return 0;
}


